using System;
using System.Runtime.CompilerServices;
using System.Collections.Generic;
using System.Threading;

//
// * Copyright (c) 2002-2009 "Neo Technology,"
// *     Network Engine for Objects in Lund AB [http://neotechnology.com]
// *
// * This file is part of Neo4j.
// * 
// * Neo4j is free software: you can redistribute it and/or modify
// * it under the terms of the GNU Affero General Public License as
// * published by the Free Software Foundation, either version 3 of the
// * License, or (at your option) any later version.
// * 
// * This program is distributed in the hope that it will be useful,
// * but WITHOUT ANY WARRANTY; without even the implied warranty of
// * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// * GNU Affero General Public License for more details.
// * 
// * You should have received a copy of the GNU Affero General Public License
// * along with this program. If not, see <http://www.gnu.org/licenses/>.
// 
namespace org.neo4j.kernel.impl.transaction
{

	using DeadlockDetectedException = org.neo4j.kernel.impl.transaction.DeadlockDetectedException;
	using LockManager = org.neo4j.kernel.impl.transaction.LockManager;

	using Test = junit.framework.Test;
	using TestCase = junit.framework.TestCase;
	using TestSuite = junit.framework.TestSuite;

	public class TestDeadlockDetection : TestCase
	{
		public TestDeadlockDetection(string name) : base(name)
		{
		}

		private static LockManager lm = new LockManager(new PlaceboTm());

		public static Test suite()
		{
			return new TestSuite(typeof(TestDeadlockDetection));
		}

		private class HelperThread : Thread
		{
			private const int DO_NOTHING_TASK = 0;
			private const int GET_WRITELOCK_TASK = 1;
			private const int GET_READLOCK_TASK = 2;
			private const int RELEASE_WRITELOCK_TASK = 3;
			private const int RELEASE_READLOCK_TASK = 4;
			private const int QUIT_TASK = 5;

			private string name = null;
			private int nextTask = 0;
			private bool taskCompleted = true;
			private object resource = null;
			private bool deadlockOnLastWait = false;

			internal HelperThread(string name) : base()
			{
				this.name = name;
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			public virtual void run()
			{
				try
				{
					while (nextTask != QUIT_TASK)
					{
						switch (nextTask)
						{
							case DO_NOTHING_TASK:
								wait(10);
								break;
							case GET_WRITELOCK_TASK:
								try
								{
									lm.getWriteLock(this.resource);
									deadlockOnLastWait = false;
								}
								catch (DeadlockDetectedException e)
								{
									deadlockOnLastWait = true;
								}
								taskCompleted = true;
								nextTask = DO_NOTHING_TASK;
								break;
							case GET_READLOCK_TASK:
								try
								{
									lm.getReadLock(this.resource);
									deadlockOnLastWait = false;
								}
								catch (DeadlockDetectedException e)
								{
									deadlockOnLastWait = true;
								}
								taskCompleted = true;
								nextTask = DO_NOTHING_TASK;
								break;
							case RELEASE_WRITELOCK_TASK:
								lm.releaseWriteLock(this.resource);
								taskCompleted = true;
								nextTask = DO_NOTHING_TASK;
								break;
							case RELEASE_READLOCK_TASK:
								lm.releaseReadLock(this.resource);
								taskCompleted = true;
								nextTask = DO_NOTHING_TASK;
								break;
							case QUIT_TASK:
								break;
							default:
								throw new RuntimeException("Unknown task " + nextTask);
						}
					}
				}
				catch (Exception e)
				{
					taskCompleted = true;
					Console.WriteLine("" + this + " unable to execute task, " + e);
					e.printStackTrace();
					throw new RuntimeException(e);
				}
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			internal virtual void waitForCompletionOfTask()
			{
				while (!taskCompleted)
				{
					try
					{
						wait(20);
					}
					catch (InterruptedException e)
					{
					}
				}
			}

			internal virtual bool isLastGetLockDeadLock()
			{
				return deadlockOnLastWait;
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			internal virtual void getWriteLock(object resource)
			{
				if (!taskCompleted)
				{
					throw new RuntimeException("Previous task not completed");
				}
				this.resource = resource;
				taskCompleted = false;
				nextTask = GET_WRITELOCK_TASK;
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			internal virtual void getReadLock(object resource)
			{
				if (!taskCompleted)
				{
					throw new RuntimeException("Previous task not completed");
				}
				this.resource = resource;
				taskCompleted = false;
				nextTask = GET_READLOCK_TASK;
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			internal virtual void releaseWriteLock(object resource)
			{
				if (!taskCompleted)
				{
					throw new RuntimeException("Previous task not completed");
				}
				this.resource = resource;
				taskCompleted = false;
				nextTask = RELEASE_WRITELOCK_TASK;
			}

			[MethodImpl(MethodImplOptions.Synchronized)]
			internal virtual void releaseReadLock(object resource)
			{
				if (!taskCompleted)
				{
					throw new RuntimeException("Previous task not completed");
				}
				this.resource = resource;
				taskCompleted = false;
				nextTask = RELEASE_READLOCK_TASK;
			}

			internal virtual void quit()
			{
				this.resource = null;
				taskCompleted = false;
				nextTask = QUIT_TASK;
			}

			public override string ToString()
			{
				return name;
			}
		}

		private class ResourceObject
		{
			private string name = null;

			internal ResourceObject(string name)
			{
				this.name = name;
			}

			public override string ToString()
			{
				return this.name;
			}
		}

		public virtual void testDeadlockDetection()
		{
			object r1 = new ResourceObject("R1");
			object r2 = new ResourceObject("R2");
			object r3 = new ResourceObject("R3");
			object r4 = new ResourceObject("R4");

			HelperThread t1 = new HelperThread("T1");
			HelperThread t2 = new HelperThread("T2");
			HelperThread t3 = new HelperThread("T3");
			HelperThread t4 = new HelperThread("T4");

			try
			{
				t1.Start();
				t2.Start();
				t3.Start();
				t4.Start();

				t1.getReadLock(r1);
				t1.waitForCompletionOfTask();
				t1.getReadLock(r4);
				t1.waitForCompletionOfTask();
				t2.getReadLock(r2);
				t2.waitForCompletionOfTask();
				t2.getReadLock(r3);
				t2.waitForCompletionOfTask();
				t3.getReadLock(r3);
				t3.waitForCompletionOfTask();
				t3.getWriteLock(r1);
			// t3-r1-t1
				t2.getWriteLock(r4);
				sleepSome();
			// t2-r4-t1
				t1.getWriteLock(r2);
				t1.waitForCompletionOfTask();
				assertTrue(t1.isLastGetLockDeadLock()); // t1-r2-t2-r4-t1
			// resolve and try one more time
				t1.releaseReadLock(r4);
				t2.waitForCompletionOfTask(); // will give r4 to t2
				t1.getWriteLock(r2);
			// t1-r2-t2
				t2.releaseReadLock(r2);
				t1.waitForCompletionOfTask(); // will give r2 to t1
				t1.getWriteLock(r4); // t1-r4-t2
			// dead lock
				sleepSome();
				t2.getWriteLock(r2);
				t2.waitForCompletionOfTask();
				assertTrue(t2.isLastGetLockDeadLock());
			// t2-r2-t3-r1-t1-r4-t2 or t2-r2-t1-r4-t2
				t2.releaseWriteLock(r4);
				t1.waitForCompletionOfTask(); // give r4 to t1
				t1.releaseWriteLock(r4);
				t2.getReadLock(r4);
				t2.waitForCompletionOfTask();
				t1.releaseWriteLock(r2);
				t1.waitForCompletionOfTask();
				t1.getReadLock(r2);
				t1.waitForCompletionOfTask();
				t1.releaseReadLock(r1);
				t3.waitForCompletionOfTask(); // give r1 to t3
				t3.getReadLock(r2);
				t3.waitForCompletionOfTask();
				t3.releaseWriteLock(r1);
				t1.getReadLock(r1);
				t1.waitForCompletionOfTask(); // give r1->t1
				t1.getWriteLock(r4);
				t3.getWriteLock(r1);
				t4.getReadLock(r2);
				t4.waitForCompletionOfTask();
			// deadlock
				t2.getWriteLock(r2);
				t2.waitForCompletionOfTask();
				assertTrue(t2.isLastGetLockDeadLock());
			// t2-r2-t3-r1-t1-r4-t2
			// resolve
				t2.releaseReadLock(r4);
				t1.waitForCompletionOfTask();
				t1.releaseWriteLock(r4);
				t1.waitForCompletionOfTask();
				t1.releaseReadLock(r1);
				t1.waitForCompletionOfTask();
				t2.getReadLock(r4);
				t3.waitForCompletionOfTask(); // give r1 to t3
				t3.releaseWriteLock(r1);
				t1.getReadLock(r1);
				t1.waitForCompletionOfTask(); // give r1 to t1
				t1.getWriteLock(r4);
				t3.releaseReadLock(r2);
				t3.waitForCompletionOfTask();
				t3.getWriteLock(r1);
			// cleanup
				t2.releaseReadLock(r4);
				t1.waitForCompletionOfTask(); // give r4 to t1
				t1.releaseWriteLock(r4);
				t1.waitForCompletionOfTask();
				t1.releaseReadLock(r1);
				t3.waitForCompletionOfTask(); // give r1 to t3
				t3.releaseWriteLock(r1);
				t3.waitForCompletionOfTask();
				t1.releaseReadLock(r2);
				t4.releaseReadLock(r2);
				t2.releaseReadLock(r3);
				t3.releaseReadLock(r3);
				t1.waitForCompletionOfTask();
				t2.waitForCompletionOfTask();
				t3.waitForCompletionOfTask();
				t4.waitForCompletionOfTask();
			// -- special case...
				t1.getReadLock(r1);
				t1.waitForCompletionOfTask();
				t2.getReadLock(r1);
				t2.waitForCompletionOfTask();
				t1.getWriteLock(r1); // t1->r1-t1&t2
				sleepSome();
				t2.getWriteLock(r1);
				t2.waitForCompletionOfTask();
				assertTrue(t2.isLastGetLockDeadLock());
			// t2->r1->t1->r1->t2
				t2.releaseReadLock(r1);
				t1.waitForCompletionOfTask();
				t1.releaseReadLock(r1);
				t1.waitForCompletionOfTask();
				t1.releaseWriteLock(r1);
				t1.waitForCompletionOfTask();
			}
			catch (Exception e)
			{
			// RagManager.getManager().dumpStack();
			// LockManager.getManager().dumpRagStack();
				e.printStackTrace();
				fail("Deadlock detection failed" + e);
			}
			finally
			{
				t1.quit();
				t2.quit();
				t3.quit();
				t4.quit();
			}
		}

		private void sleepSome()
		{
			try
			{
				Thread.Sleep(1000);
			}
			catch (InterruptedException e)
			{
			}
		}

		public class StressThread : Thread
		{
			private static System.Random rand = new System.Random(System.currentTimeMillis());
			private static readonly object READ = new object();
			private static readonly object WRITE = new object();
			private static ResourceObject[] resources = new ResourceObject[10];

			private static bool go = false;

			private string name;
			private int numberOfIterations;
			private int depthCount;
			private float readWriteRatio;

			internal StressThread(string name, int numberOfIterations, int depthCount, float readWriteRatio) : base()
			{
				this.name = name;
				this.numberOfIterations = numberOfIterations;
				this.depthCount = depthCount;
				this.readWriteRatio = readWriteRatio;
			}

			public virtual void run()
			{
				try
				{
					while (!go)
					{
						try
						{
							sleep(100);
						}
						catch (InterruptedException e)
						{
						}
					}
					Stack<object> lockStack = new Stack<object>();
					Stack<ResourceObject> resourceStack = new Stack<ResourceObject>();
					try
					{
						for (int i = 0; i < numberOfIterations; i++)
						{
							int depth = depthCount;
							do
							{
								float f = rand.nextFloat();
								int n = rand.Next(resources.Length);
								if (f < readWriteRatio)
								{
									lm.getReadLock(resources[n]);
									lockStack.Push(READ);
								}
								else
								{
									lm.getWriteLock(resources[n]);
									lockStack.Push(WRITE);
								}
								resourceStack.Push(resources[n]);
							}
							while (--depth > 0);
//                        
//                         * try { sleep( rand.nextInt( 100 ) ); } catch (
//                         * InterruptedException e ) {}
//                         
							while (!lockStack.isEmpty())
							{
								if (lockStack.Pop() == READ)
								{
									lm.releaseReadLock(resourceStack.Pop());
								}
								else
								{
									lm.releaseWriteLock(resourceStack.Pop());
								}
							}
						}
					}
					catch (DeadlockDetectedException e)
					{
					// System.out.println( "Deadlock detected!" );
					}
					finally
					{
						while (!lockStack.isEmpty())
						{
							if (lockStack.Pop() == READ)
							{
								lm.releaseReadLock(resourceStack.Pop());
							}
							else
							{
								lm.releaseWriteLock(resourceStack.Pop());
							}
						}
					}
				}
				catch (Exception e)
				{
					e.printStackTrace();
					throw new RuntimeException(e);
				}
			}

			public override string ToString()
			{
				return this.name;
			}
		}

		public virtual void testStressMultipleThreads()
		{
			for (int i = 0; i < StressThread.resources.length; i++)
			{
				StressThread.resources[i] = new ResourceObject("RX" + i);
			}
			Thread[] stressThreads = new Thread[50];
			StressThread.go = false;
			for (int i = 0; i < stressThreads.Length; i++)
			{
				stressThreads[i] = new StressThread("T" + i, 100, 10, 0.80f);
			}
			for (int i = 0; i < stressThreads.Length; i++)
			{
				stressThreads[i].Start();
			}
			StressThread.go = true;
		}
	}
}